//
// Created by lfm on 2025/2/26.
//
//给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
//子数组是数组中的一个连续部分。
//示例 1：
//输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
//输出：6
//解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
//示例 2：
//输入：nums = [1]
//输出：1
//示例 3：
//输入：nums = [5,4,-1,7,8]
//输出：23
//提示：
//1 <= nums.length <= 105
//-104 <= nums[i] <= 104
//class Solution
//{
//public:
//    int dfs(int x,  int sum, vector<int> & nums)
//    {
//        int sum = 0;
//        int take = 0;
//        take = dfs(x + 1, sum + nums[i],nums);
//        int no_take = dfs(x + 1, sum, nums);
//        sum = max(no_take, take);
//        return sum;
//    }
//    int maxSubArray(vector<int>& nums)
//    {
//        int ans = dfs(0,  0,nums);
//        return ans;
//    }
//};
const int N = 10010;
class Solution
{
public:
    int mem[N];
    int dfs(int x, vector<int> & nums)//x为下标，nums[x]代表当前以nums[x]为结尾的连续子数组，
    // 将它的和求出,与num[x - 1]为结尾的数组的和比较
    {
        if (x < 0)
            return 0;
        if (mem[x])
            return mem[x];
        int res = -1e9;
        res = max(nums[x], nums[x] + dfs(x - 1, nums));
        mem[x] = res;
        return res;
    }
    int maxSubArray(vector<int>& nums)
    {
        int ans = -1e9;
        int n = nums.size();
        int dp[N];
//        for (int i = 0; i < nums.size(); i++)
//        {
//            ans = max(ans, dfs(i, nums));
//        }
        for (int i = 0; i < n; i++)
        {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
        }
        for (int i = 0; i < n; i++)
        {
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};
